# 作者: 赵若云
# 2025年02月25日15时35分40秒
# 3478783573@qq.com

# python的sort使用的就是归并排序

import random


class Sort:
    def __init__(self, count, nums_range):
        """
        排序
        :param count: 排序的数目
        """
        self.count = count
        self.nums_range = nums_range  # 数的范围
        self.arr = []  # 数组
        self.random_nums()  # 生成初始数组

    def random_nums(self):
        for i in range(self.count):
            self.arr.append(random.randint(0, self.nums_range - 1))

    def partition(self, left, right):
        arr = self.arr
        k = left
        for i in range(left, right):
            if arr[i] < arr[right]:
                arr[i], arr[k] = arr[k], arr[i]
                k += 1
        arr[k], arr[right] = arr[right], arr[k]
        return k

    def quick_sort(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick_sort(left, pivot - 1)
            self.quick_sort(pivot + 1, right)

    def adjust_max_heap(self, parent_pos, arr_len):
        """
        把某一棵字数调整为大根堆
        :param parent_pos: 要调整的位置
        :param arr_len: 列表长度
        :return:
        """
        dad = parent_pos
        son = parent_pos * 2 + 1
        while son < arr_len:
            if son + 1 < arr_len and self.arr[son] < self.arr[son + 1]:
                son += 1
            if self.arr[dad] < self.arr[son]:
                self.arr[dad], self.arr[son] = self.arr[son] , self.arr[dad]
                dad = son
                son = 2 * dad + 1
            else:
                break

    # 堆排
    def heap_sort(self):
        arr = self.arr
        # 把列表调整为大根堆,n // 2 - 1是最后一个父亲结点的下标值
        for parent_pos in range(self.count // 2 - 1, -1,-1):  # //整除
            self.adjust_max_heap(parent_pos, self.count)
        for end_pos in range(self.count - 1, 0, -1):
            arr[end_pos], arr[0] = arr[0], arr[end_pos]
            self.adjust_max_heap(0, end_pos)


if __name__ == '__main__':
    s = Sort(10, 100)
    print(s.arr)
    # s.quick_sort(0, s.count - 1)
    # print(s.arr)
    s.heap_sort()
    print(s.arr)
